package com.lxw.question;

public class Q19 {
    /**
     * 题目描述
     * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
     * 链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof
     */

    /**
     * 超时的题解
     * @param a
     * @return
     */
    public int[] constructArr(int[] a) {
        if(a == null || a.length == 0){
            return new int[]{};
        }

        int len = a.length;
        int b[] = new int[len];
        for(int k = 0 ; k < len ; k++){
            b[k] = 1;
        }
        for(int i = 0 ; i < len ; i++){
            for(int j = 0 ; j < len ; j++){
                if(j == i){
                    continue;
                }
                b[i] = b[i] * a[j];
            }
        }
        return b;
    }

    /**
     * 违规的题解（题目规定不能用除法)
     * @param a
     * @return
     */
    public int[] constructArr2(int[] a){
        if(a == null || a.length == 0){
            return new int[]{};
        }

        int len = a.length;

        int sum = 1;

        for(int i = 0 ; i < len ; i++){
            sum = sum * a[i];
        }

        int b[] = new int[len];

        for(int j = 0 ; j < len ; j++){
            b[j] = sum / a[j];
        }
        return b;
    }

    public int[] constructArr3(int[] a){
        if(a == null || a.length == 0){
            return new int[]{};
        }

        int len = a.length;

        int[] b = new int[len];

        /**从左边开始遍历，计算数组左边的乘积**/
        for(int i = 0,product = 1; i < len ; i++){
            b[i] = product;
            product = product * a[i];
        }

        for(int i = len - 1,product = 1; i >= 0 ; i--){
            b[i] = product * b[i];
            product = product * a[i];
        }

        return b;
    }
}
